package com.zjsru.oneDay202203;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: likew
 * @Date: 2022/3/23
 *
 * 字典序的第K小数字
 * 给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。
 *
 * 字典序:
 * 简而言之，就是根据数字的前缀进行排序，
 * 比如 10 < 9，因为 10 的前缀是 1，比 9 小。
 * 再比如 112 < 12，因为 112 的前缀 11 小于 12。
 * 这样排序下来，会跟平常的升序排序会有非常大的不同。先给你一个直观的感受，一个数乘 10，或者加 1，哪个大？可能你会吃惊，后者会更大。
 *
 *
 * 输入: n = 13, k = 2
 * 输出: 10
 * 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
 *
 */
public class findKthNumber {
    public int findKthNumber(int n, int k) {
        int ans = 1;
        while(k > 1){
            int cnt = getCnt(ans,n);
            if(cnt < k){
                k -= cnt;
                ans ++;
            } else{
                k--;
                ans *= 10;
            }
        }
        return ans;
    }
    
    private int getCnt(int x, int limit) {
        String a = String.valueOf(x),b = String.valueOf(limit);
        int n = a.length(), m = b.length(),k =m -n;
        int ans = 0,u = Integer.parseInt(b.substring(0,n));
        for(int i = 0;i<k;i++){
            ans += Math.pow(10,i);
        }
        if(u > x) ans += Math.pow(10,k);
        else if (u == x) ans += limit - x*Math.pow(10,k)+1;
        return ans;
    }
    
    public static void main(String[] args) {
        findKthNumber findKthNumber = new findKthNumber();
        int n = 13,k =2;
        System.out.println(findKthNumber.findKthNumber(n, k));
    }
}
